package com.leetcode.linkedlist;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2019/10/8
 * @description: 21. 合并两个有序链表
 * A
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 * <p>
 * 示例：
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MergeTwoLists21 {

	public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null) {
			return l2;
		}
		if (l2 == null) {
			return l1;
		}

		///1.构造 dummy 节点，返回 dummy.next 即可( dummy 节点不是每个链表问题都需要使用的，只是需要创建新链表时为了防止头节点复杂判断的情况而使用的小技巧)
		ListNode dummy = new ListNode(-1);

		ListNode curl1 = l1;
		ListNode curl2 = l2;
		ListNode cur=dummy;
///指针指向原两个节点
		while (curl1 != null && curl2 != null) {
			 if (curl1.val<curl2.val){
			 	cur.next=curl1;
			 	curl1=curl1.next;
			 }else {
				 cur.next=curl2;
				 curl2=curl2.next;
			 }
			 ///每次执行时 cur 跳到下一个节点
			 cur=cur.next;
		}
		///如果 l1 已经结束
		if (curl1==null){
			while (curl2!=null){
				cur.next=curl2;
				curl2=curl2.next;

				cur=cur.next;
			}

		}else{
			while (curl1!=null){
				cur.next=curl1;
				curl1=curl1.next;

				cur=cur.next;
			}
		}

		return dummy.next;
	}

	/**
	 * 优化版本
	 * @param l1
	 * @param l2
	 * @return
	 */
	public static ListNode mergeTwoListsOptimizeVersion(ListNode l1, ListNode l2){
		if (l1 == null) {
			return l2;
		}
		if (l2 == null) {
			return l1;
		}

		///1.构造 dummy 节点，返回 dummy.next 即可( dummy 节点不是每个链表问题都需要使用的，只是需要创建新链表时为了防止头节点复杂判断的情况而使用的小技巧)
		ListNode dummy = new ListNode(-1);

		ListNode curl1 = l1;
		ListNode curl2 = l2;
		ListNode cur=dummy;
///指针指向原两个节点
		while (curl1 != null && curl2 != null) {
			if (curl1.val<curl2.val){
				cur.next=curl1;
				curl1=curl1.next;
			}else {
				cur.next=curl2;
				curl2=curl2.next;
			}
			///每次执行时 cur 跳到下一个节点
			cur=cur.next;
		}
		///如果 l1 已经结束
		///todo:Optimize-让 cur 直接指向 未完的节点
		if (curl1==null){
			cur.next=curl2;
		}else{
			cur.next=curl1;
		}

		return dummy.next;
	}

	public static void main(String[] args) {
		ListNode node4 = new ListNode(4);
		ListNode node2 = new ListNode(2);
		node2.next = node4;
		ListNode node1 = new ListNode(1);
		node1.next = node2;

		ListNode node2_3 = new ListNode(3);
		ListNode node2_2 = new ListNode(2);
		node2_2.next = node2_3;
		ListNode node2_1 = new ListNode(1);
		node2_1.next = node2_2;


		ListNode node = mergeTwoLists(node1, node2_1);
ListNode.print(node);
	}
}
